使用邻接矩阵实现最小生成树Prim算法 （含注释） |
您所在的位置：网站首页 › easywebui 树 › 使用邻接矩阵实现最小生成树Prim算法 （含注释） |
|
题目描述： 用邻接矩阵存储无向图，实现最小生成树Prim算法，图中边的权值为整型，顶点个数少于10个。 输入描述 首先输入图中顶点个数和边的条数； 再输入顶点的信息（字符型）； 再输入各边及其权值。 输出描述 输出从编号为0的顶点开始的Prim算法最小生成树中的各边及其权值，每条边及其权值占一行。 输入样例 5 7 A B C D E 0 1 6 0 2 2 0 3 1 1 2 4 1 3 3 2 4 6 3 4 7 输出样例 A D 1 A C 2 D B 3 C E 6第一种方法 #include using namespace std; #define MAX 20 #define INIFINTY 65535//理想无穷大 typedef struct { int arc[MAX][MAX];//权重 char vertex[MAX];//顶点数据 int numVertexes, numEdges;//顶点大小和边长度 }MGraph; void CreateMGraph(MGraph * G,int n,int e){ int i, j; G->numVertexes = n; G->numEdges = e; for (i = 0; i < G->numVertexes; i++) { // 初始化图（自反的为零，非自反的为无穷大） for (j = 0; j < G->numVertexes; j++) { if (i == j)//自反 G->arc[i][j] = 0; else//非自反 G->arc[i][j] = G->arc[j][i] = INIFINTY; //对称矩阵 } } for(int i = 0;i < n; i++)//存储顶点值 cin>>G->vertex[i]; int i1,i2,i3; for(int i = 0; i < e; i++)//存储边顶点坐标和边的权重 { cin>>i1>>i2>>i3; G->arc[i1][i2] = i3,G->arc[i2][i1]=i3;//对称 } } // Prime算法生成最小生成树 void MinPrim(MGraph G){ int min,i,j,k; int adjvex[MAX]; // 保存相关顶点的下标 int lowcost[MAX]; // 保存相关顶点间边的权值 lowcost[0] = 0; // 初始化第一个权值为0，即v0加入生成树 adjvex[0] = 0; // 初始化第一个顶点下标为0 for (i = 1; i < G.numVertexes; i++) { // 循环除下标为0外的全部顶点 lowcost[i] = G.arc[0][i]; // 将v0顶点与之右边的权值存入数组 adjvex[i] = 0; // 初始化都为v0的下标 } for (i = 1; i < G.numVertexes; i++) { min = INIFINTY; //初始化最小权值 j = 1; k = 0; while (j < G.numVertexes) { // 循环全部顶点 if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; // 让当前权值变为最小值 k = j; // 将当前最小值的下标存入k } j++; } cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |